package com.example.sort;

/**
 * 计数排序
 */
public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;
        // 找出数组中的最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            } else if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 创建计数数组
        int[] count = new int[max - min + 1];
        // 统计每个元素出现的次数
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }
        // 计算累计计数
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        // 创建输出数组
        int[] output = new int[arr.length];
        // 将元素放置在正确的位置
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        // 将排序后的数组复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 0, 2, 3, 0, 3};
        countingSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}